package com.wenhai.liuyubobobo.imooc.search;


/**
 * 第四版并查集实现 基于数：子树指向父节点 记录数的高度 rank 路径压缩
 *
 * @author wenhai
 * @date   2021/3/29
 */
public class UnionFind5 implements UnionFind {
    private final int[] parent;
    private final int[] rank;

    public UnionFind5(int size) {
        parent = new int[size];
        rank   = new int[size];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            rank[i]   = 1;
        }
    }


    @Override
    public int size(){
     return parent.length;
    }

    @Override
    public void union(int q, int p){
        int qRoot = find(q);
        int pRoot = find(p);
        if (qRoot == pRoot) {
            return;
        }
        if (rank[qRoot] < rank[pRoot]) {
            parent[qRoot] = pRoot;

        } else if (rank[qRoot] > rank[pRoot]) {
            parent[pRoot] = qRoot;
        } else {
            parent[pRoot] = qRoot;
            rank[qRoot] += 1;
        }
    }

    @Override
    public boolean isConnected(int q, int p){
        return find(q) == find(p);
    }

    private int find(int index) {
        if (index < 0 || index >= parent.length) {
            throw new IndexOutOfBoundsException(String.valueOf(index));
        }
        while (index != parent[index]) {
            parent[index] = parent[parent[index]];
            index = parent[index];
        }
        return parent[index];
    }


}
